package sort;

import edu.princeton.cs.algs4.StdOut;

public class Insertion extends Example {
  public static void sort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
      // 从当前j索引向前移动，如果j索引值小于j-1值则交换
      // 当前索引之前是已排序元素
      // i = 3时： 2,4,8,3,6,7,5
      // for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
      // exch(a, j, j - 1);
      // }
      Comparable temp = a[i]; // 缓存当前索引值
      int j = i;
      // 向后移动大于当前索引的值
      while (j > 0 && less(temp, a[j - 1])) {
        a[j] = a[j - 1];
        j--;
      }
      a[j] = temp;
    }
  }

  public static void main(String[] args) {
    Integer[] a = { 2, 4, 8, 3, 6, 7, 9, 5 };
    Insertion.sort(a);
  }
}
